package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href='https://leetcode.cn/problems/next-greater-node-in-linked-list/'>链表中的下一个更大节点(Next Greater Node In Linked List)</a>
 * <p>给定一个长度为 n 的链表 head</p>
 * <p>对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。</p>
 * <p>返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [2,1,5]
 *      输出：[5,5,0]
 *
 * 示例 2：
 *      输入：head = [2,7,4,3,5]
 *      输出：[7,0,5,5,0]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表的结点数范围是 [1, 100]</li>
 *     <li>1 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/8 16:08
 */
public class LC1019NextGreaterNodeInLinkedList_M {
    static class Solution {
        public int[] nextLargerNodes(ListNode head) {
            // 计算链表的长度，返回值的长度恰好为链表的长度
            int length = 0;
            ListNode currNode = head;
            while (currNode != null) {
                ++length;
                currNode = currNode.next;
            }
            int[] ans = new int[length];
            // 使用单调栈，同时将每个节点封装成 int[]，index-0 为值，index-1 为下标
            Deque<int[]> stack = new LinkedList<>();
            for (int idx = 0; idx < length; idx++) {
                int currNodeVal = head.val;
                if (!stack.isEmpty()) {
                    while (!stack.isEmpty() && currNodeVal > stack.peekFirst()[0]) {
                        int[] ints = stack.removeFirst();
                        ans[ints[1]] = currNodeVal;
                    }
                }
                stack.addFirst(new int[]{currNodeVal, idx});
                head = head.next;
            }
            return ans;
        }
    }
}
